\section{XPath}
\label{preliminary}

An XPath query in this paper starts from the root and consists of one or more \emph{steps}. Each step consists of an \emph{axis}, a \emph{name test}, and at most one \emph{predicate}.  An axis defines a set of nodes relative to the nodes matched for the steps so far. We can use eleven axes as defined in Fig~\figurename{fig:grammar}.
A name test is used for selecting nodes: if the name of a tag in an XML document is equal to the name test, the node is selected.  A predicate written between ``\verb|[|'' and ``\verb|]|'' describes additional conditions on the matched nodes by using a path without predicates. For example, ``\verb|/descendant::a/child::b[following-|\verb|sibling::d]|'' is an XPath query with two steps where \verb|descendant| 
and \verb|child| are the axes, \verb|a| and \verb|b| are the name tests, and a predicate \verb|following-sibling::d| is attached to the second step. This query first retrieves all the nodes with name \verb|a| in an XML document, and then among their children it retrieves node \verb|b| with one or more following siblings with name \verb|d|. In other words, the result of the query is a set of nodes \verb|b| that has its parent \verb|a| and at least one sibling \verb|d| on its right.

\begin{figure}
	\centering\fbox{
		\begin{minipage}{.98\linewidth}
			\textit{Query} ::= `\texttt{/}' \textit{LocationPath}          \\
			\textit{LocationPath} ::= \textit{Step} $~|~$ \textit{Step} `\texttt{/}' \textit{LocationPath}          \\
			\textit{Step} ::= \textit{AxisName} `\texttt{::}' \textit{NameTest} \textit{Predicate}?          \\
			\textit{AxisName} ::= `\texttt{self}' $~|~$ `\texttt{child}' $~|~$ `\texttt{parent}'   $~|~$ `\texttt{descendant}'   $~|~$ `\texttt{ancestor}'          \\ 
			\phantom{\textit{AxisName} :}  `\texttt{descendant-or-self}' $~|~$ `\texttt{ancestor-or-self}'  $~|~$ `\texttt{following}'    \\
			\phantom{\textit{AxisName} :}        $~|~$ `\texttt{following-sibling}'  $~|~$ `\texttt{preceding}  $~|~$ `\texttt{preceding-sibling}'          \\
			\textit{NameTest} ::= `\texttt{*}' $~|~$ \textit{string}	          \\
			\textit{Predicate} ::= `\texttt{[}' \textit{SimpleLocationPath} `\texttt{]}'          \\
			\textit{SimpleLocationPath} ::= \textit{SimpleStep} $~|~$ \textit{SimpleStep} `\texttt{/}' \textit{SimpleLocationPath}          \\
			\textit{SimpleStep} ::= \textit{AxisName} `\texttt{::}' \textit{NameTest}          
		\end{minipage}
	}
	\caption{Grammars of XPath queries used in this paper}
	\label{fig:grammar}
\end{figure}